هياكل البيانات: القوائم المترابطة Linked Lists والأشجار Trees في لغة سي C

تُعتبر هياكل البيانات من الركائز الأساسية في علوم الحاسوب، حيث تمثل الوسيلة التي تُخزن بها البيانات داخل الذاكرة بطريقة منظمة، تسهل معالجتها والوصول إليها بفعالية. من بين أكثر هياكل البيانات استخدامًا وانتشارًا في البرمجة، خصوصًا في لغة C، تأتي القوائم المترابطة (Linked Lists) والأشجار (Trees) كأدوات قوية ومرنة لتنظيم البيانات بطرق تتناسب مع متطلبات مختلفة من حيث السرعة، السعة، وسهولة التعديل.

في هذا المقال سوف نغوص في عمق هذين النوعين من هياكل البيانات، نشرح مفاهيمهما، طرق تنفيذهما في لغة C، مزاياهما وعيوبهما، إضافة إلى تطبيقات عملية تساعد على استيعاب الفكرة وتوضيح أهمية استخدامهما في البرمجة.

مفهوم هياكل البيانات

قبل الخوض في التفاصيل، يجدر توضيح مفهوم هياكل البيانات بشكل عام. هياكل البيانات هي طريقة تنظيم البيانات في ذاكرة الحاسوب بحيث يمكن استخدامها بكفاءة عالية. هناك العديد من أنواع هياكل البيانات مثل المصفوفات، القوائم، الأشجار، الرسوم البيانية، الجداول الهاش، وغيرها.

كل نوع من هذه الهياكل له خصائصه التي تجعله مناسبًا لمواقف معينة. مثلاً، المصفوفات توفر وصولًا سريعًا لعناصرها حسب الفهرس، لكنها ثابتة الحجم. بالمقابل، القوائم المترابطة يمكنها النمو أو الانكماش ديناميكيًا أثناء التنفيذ.

القوائم المترابطة Linked Lists

التعريف والمفهوم

القائمة المترابطة هي مجموعة من العقد (Nodes) التي ترتبط كل عقدة منها بالعقدة التي تليها من خلال مؤشر. تحتوي كل عقدة عادة على عنصر بيانات (Data) ومؤشر (Pointer) يشير إلى العقدة التالية في القائمة.

تختلف القوائم المترابطة عن المصفوفات بأن حجمها غير ثابت، ويمكن التعديل عليها بسهولة بإضافة أو حذف عقد دون الحاجة لتحريك العناصر الأخرى، بخلاف المصفوفة التي قد تتطلب إعادة تخصيص كامل للمصفوفة عند التعديل.

أنواع القوائم المترابطة

• القائمة المترابطة الأحادية (Singly Linked List): كل عقدة تحتوي على بيانات ومؤشر يشير إلى العقدة التالية فقط.

• القائمة المترابطة الثنائية (Doubly Linked List): كل عقدة تحتوي على بيانات، مؤشر للعقدة التالية، ومؤشر للعقدة السابقة.

• القائمة الدائرية (Circular Linked List): هي قائمة مترابطة يكون المؤشر في العقدة الأخيرة يشير إلى العقدة الأولى، مما يجعل القائمة حلقة دائرية.

تمثيل القائمة المترابطة الأحادية في لغة C

c
CopyEdit
#include 
#include 

// تعريف هيكل العقدة
struct Node {
    int data;
    struct Node* next;
};

// إنشاء عقدة جديدة
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    if (!newNode) {
        printf("خطأ في تخصيص الذاكرة\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// إضافة عقدة في بداية القائمة
void insertAtBeginning(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

// طباعة عناصر القائمة
void printList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;

    insertAtBeginning(&head, 10);
    insertAtBeginning(&head, 20);
    insertAtBeginning(&head, 30);

    printList(head);

    return 0;
}

مزايا القوائم المترابطة

• ديناميكية الحجم: يمكن تعديل حجم القائمة أثناء التشغيل.

• سهولة الإدخال والحذف: لا تتطلب تحريك العناصر الأخرى كما في المصفوفة.

• توفير في الذاكرة: لا حاجة لحجز مساحة كبيرة مسبقًا.

عيوب القوائم المترابطة

• الوصول العشوائي بطيء: لا يمكن الوصول إلى عنصر معين بسرعة لأنه يجب المرور عبر العناصر من البداية.

• استهلاك إضافي للذاكرة: كل عقدة تحتاج إلى مؤشر إضافي يشغل مساحة.

الأشجار Trees

التعريف والمفهوم

الأشجار هي هيكل بيانات غير خطي (Non-linear Data Structure)، تتكون من عقد (Nodes) مترابطة على شكل هيكل شجري، حيث تحتوي العقدة الرئيسية أو الجذر (Root) على أبناء (Children)، وكل ابن يمكن أن يحتوي على أبناء آخرين، وهكذا. لا تحتوي العقد في الشجرة على حلقة، أي لا يمكن للعقدة أن تكون جزءًا من نفسها بشكل غير مباشر.

تمثل الأشجار علاقات هرمية بين العناصر، وهي تستخدم في تمثيل البيانات التي تحتاج إلى تنظيم هرمي أو متداخل مثل قواعد البيانات، أنظمة الملفات، تراكيب البيانات في البرمجة، وغيرها.

أنواع الأشجار

• شجرة ثنائية (Binary Tree): كل عقدة تحتوي على ما لا يزيد عن ابنين، يسار ويمين.

• شجرة البحث الثنائية (Binary Search Tree – BST): شجرة ثنائية يكون فيها العقد في الجانب الأيسر أقل قيمة من العقدة الأم، والعقد في الجانب الأيمن أكبر.

• شجرة AVL: شجرة بحث ثنائية متوازنة ذاتيًا لتحسين سرعة عمليات البحث.

• شجرة B-Tree و B+ Tree: تستخدم في قواعد البيانات وأنظمة الملفات.

تمثيل الشجرة الثنائية في لغة C

c
CopyEdit
#include 
#include 

// تعريف هيكل عقدة الشجرة
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// إنشاء عقدة جديدة
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    if (!newNode) {
        printf("خطأ في تخصيص الذاكرة\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// إضافة عقدة في شجرة البحث الثنائية
struct Node* insertNode(struct Node* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }
    if (data < root->data) {
        root->left = insertNode(root->left, data);
    } else if (data > root->data) {
        root->right = insertNode(root->right, data);
    }
    return root;
}

// طباعة الشجرة بطريقة Inorder
void inorderTraversal(struct Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

int main() {
    struct Node* root = NULL;

    root = insertNode(root, 50);
    insertNode(root, 30);
    insertNode(root, 70);
    insertNode(root, 20);
    insertNode(root, 40);
    insertNode(root, 60);
    insertNode(root, 80);

    printf("العناصر في الشجرة (ترتيب Inorder): ");
    inorderTraversal(root);
    printf("\n");

    return 0;
}

مزايا الأشجار

• تمثيل البيانات الهرمية: تسهل التعامل مع البيانات التي لها بنية متداخلة.

• بحث سريع: في حالة استخدام شجرة بحث ثنائية متوازنة، عمليات البحث، الإدخال، والحذف تكون فعالة.

• تنظيم وترتيب البيانات: تتيح ترتيب العناصر بطريقة منظمة.

عيوب الأشجار

• التعقيد: قد تكون إدارة توازن الشجرة معقدة بعض الشيء.

• استهلاك الذاكرة: تحتاج إلى مؤشرات إضافية (يسار ويمين) لكل عقدة.

• الاعتماد على التوازن: أداء الأشجار غير المتوازنة قد ينخفض بشكل كبير.

مقارنة بين القوائم المترابطة والأشجار

استخدامات عملية وتطبيقات للقوائم المترابطة والأشجار

القوائم المترابطة

تستخدم القوائم المترابطة في:

• تنفيذ قوائم الانتظار (Queues) والمكدسات (Stacks): حيث يمكن إضافة العناصر وحذفها بكفاءة.

• التمرير الديناميكي للبيانات: كالحفاظ على سجل تغييرات أو قوائم من العناصر المتغيرة الحجم.

• تحويل التعابير: في تطبيقات مثل تحويل التعابير الرياضية إلى أشكال أخرى باستخدام المكدسات المبنية على القوائم المترابطة.

الأشجار

الأشجار لها استخدامات واسعة:

• شجرات البحث: لتسريع عمليات البحث، خاصة في قواعد البيانات ومحركات البحث.

• هيكلة أنظمة الملفات: مثل أنظمة الملفات في أنظمة التشغيل حيث تُنظم الملفات والمجلدات في هيكل هرمي.

• تمثيل تعابير برمجية: في المترجمات (Compilers) حيث تُحول البرامج إلى شجرة بناء الجملة (Parse Tree).

• الشبكات العصبية الاصطناعية وألعاب الذكاء الاصطناعي: تستخدم في تمثيل الحالات والقرارات.

كيفية التعامل مع هياكل البيانات في لغة C

تُعتبر لغة C لغة برمجة منخفضة المستوى نسبيًا مقارنة بلغات حديثة، لكنها توفر حرية كبيرة في إدارة الذاكرة، مما يجعلها مثالية لتعلم وفهم هياكل البيانات بعمق. تتطلب القوائم المترابطة والأشجار استخدام المؤشرات والدوال الخاصة بإدارة الذاكرة مثل malloc و free لضمان تخصيص الذاكرة ديناميكيًا وتحريرها بشكل صحيح لتجنب تسرب الذاكرة (Memory Leak).

نصائح مهمة عند العمل مع القوائم المترابطة والأشجار في C

• التحقق من نجاح تخصيص الذاكرة: دائمًا تحقق من أن malloc لم تُرجع مؤشر NULL.

• تحرير الذاكرة بعد الانتهاء: يجب كتابة دوال خاصة لتحرير الذاكرة لكل عقدة لتجنب تسرب الذاكرة.

• فهم المؤشرات جيدًا: المؤشرات هي أساس التعامل مع هياكل البيانات في C، وفهمها بدقة أمر ضروري.

• تنظيم الكود: استخدم دوالًا منظمة لكل عملية (إدخال، حذف، بحث، طباعة) للحفاظ على قابلية الصيانة.

خلاصة

تمثل القوائم المترابطة والأشجار في لغة C من أهم هياكل البيانات التي تسمح بتنظيم البيانات بشكل مرن وفعال. القوائم المترابطة مناسبة للبيانات التي تحتاج إلى تعديل مستمر وحجم متغير، بينما توفر الأشجار بنية أكثر تعقيدًا لكنها تسمح بعمليات بحث وإدخال وحذف أكثر كفاءة، خصوصًا عند استخدامها في أشكال متوازنة.

تطبيق هذه الهياكل في لغة C يعزز فهم المبرمج للمؤشرات، إدارة الذاكرة، والبنية الداخلية للبيانات، وهو ما يمثل أساسًا قويًا لأي مبرمج يسعى لتطوير مهاراته في الخوارزميات وهياكل البيانات. مع الممارسة المستمرة واستخدام هذه الهياكل في مشاريع تطبيقية، يصبح من السهل استغلال قوة لغة C في بناء برمجيات فعالة وعالية الأداء.

المصادر والمراجع

• “Data Structures Using C” – Reema Thareja, 2017.

• “The C Programming Language” – Brian W. Kernighan and Dennis M. Ritchie, 1988.

هذا المقال يوفر شرحًا وافيًا وموسعًا عن القوائم المترابطة والأشجار في لغة C، مع التركيز على المفاهيم، التطبيقات، والبرمجة العملية.